#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
//此次堆排序为升序,应用大根堆
//详解：
//如果用小根堆，那么根节点确实可以排序完成，但是接下来需要在
//不删除根节点的情况下找出次小节点，而这样的操作会打乱关系
//故升序不用小根堆。同理降序不用大根堆

void swap(int* a, int* b)//交换
{
	int x = *a;
	*a = *b;
	*b = x;
}

void AdjustDown(int* hp, int n, int parent)//向下调整
{
	int child = parent * 2 + 1;//先假定左孩子是两个孩子中最大的
	while (child < n)
		//规定了child移动的范围
	{
		if (child + 1 < n && hp[child] < hp[child + 1])//child+1 < n是为了防止child+1会导致出数组规定范围，造成无效数据比较
			//当右孩子才是最大情况时
		{
			child++;//此时child就等于右孩子
		}
		if (hp[parent] < hp[child])
		{
			swap(&hp[parent], &hp[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}

void AdjustUp(int* hp, int child)//向上调整
{
	int parent = (child - 1) / 2;//找到父节点

	while (child > 0)
		//当child到0时，代表已经比较到根节点，此时已经可以停止比较
	{
		if (hp[parent] > hp[child])
			//当parent比child大时，停止比较
		{
			break;
		}

		else
		{
			swap(&hp[parent], &hp[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
	}
}

int main()
{
	int a[10] = { 5,6,15,2,5,65,1,6,95,84 };
	int i = 1;
	for (i; i < 10; i++)
	//先建堆
	{
		AdjustUp(a, i);//i从1开始，i每次都往后++，每次都只让一个数据建堆
							  //相应的，这部分的复杂度为O(n)

	}
	for (i = 10-1; i > 0 ; i--)
	//排序，因为是大根堆，所以根节点最大，就先将根节点放到最后面，然后再对新的根节点向下调整
	{
		swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
	return 0;
}